Learning probabilities from random observables in high dimensions: the maximum entropy distribution and others

摘要

We consider the problem of learning a target probability distribution over aset of $N$ binary variables from the knowledge of the expectation values (withthis target distribution) of $M$ observables, drawn uniformly at random. Thespace of all probability distributions compatible with these $M$ expectationvalues within some fixed accuracy, called version space, is studied. Weintroduce a biased measure over the version space, which gives a boostincreasing exponentially with the entropy of the distributions and with anarbitrary inverse `temperature' $\Gamma$. The choice of $\Gamma$ allows us tointerpolate smoothly between the unbiased measure over all distributions in theversion space ($\Gamma=0$) and the pointwise measure concentrated at themaximum entropy distribution ($\Gamma \to \infty$). Using the replica method wecompute the volume of the version space and other quantities of interest, suchas the distance $R$ between the target distribution and the center-of-massdistribution over the version space, as functions of $\alpha=(\log M)/N$ and$\Gamma$ for large $N$. Phase transitions at critical values of $\alpha$ arefound, corresponding to qualitative improvements in the learning of the targetdistribution and to the decrease of the distance $R$. However, for fixed$\alpha$, the distance $R$ does not vary with $\Gamma$, which means that themaximum entropy distribution is not closer to the target distribution than anyother distribution compatible with the observable values. Our results areconfirmed by Monte Carlo sampling of the version space for small system sizes($N\le 10$).